"""
投资问题，有m元钱，n个项目，每个项目k的回报由 f_k(x) 表示，即对项目k投资x元钱的回报
为 f_k(x) 的值。
求一个投资向量 X = (x1,x2,...,xn)，即对项目k的投资为xk，使得总回报最大。

目标函数：max sum f_k(x_k) for k = 1 to n
约束条件：sum x_k = m for k = 1 to n

思路：参数k和x，对于k，考虑前k个项目；对于x，考虑0到x所有可能的取值。
则dp[n][m]就是原问题。

状态转移方程：

    dp[k][x]=max{f[k][xk] + dp[k-1][xk] for xk = 0 to x}, k=2,3,...,n

边界条件：

    dp[1][x]=f[1][x]
    dp[k][0]=0, k=1,2,...,n

解释：当前考虑的项目为k，当前有的钱数为x，则依次给项目k分配0至x元钱，剩下的钱全部分给k-1子问题的最优解，
这样就得到一个方案以及相应的回报，取其中最大值就是子问题的解。

"""

M = 5  # 钱数
N = 4  # 项目数

# 收益函数。
f = {
    1: [0, 11, 12, 13, 14, 15],
    2: [0, 0, 5, 10, 15, 20],
    3: [0, 2, 10, 30, 32, 40],
    4: [0, 20, 21, 22, 23, 24],
}


def DP_Recur(k, x, mem, solution):
    """
    记忆化搜索。
    """
    if (k, x) in mem:
        return mem[k, x]
    val = None  # 该子问题的解是多少？
    amount = None  # 获得最大值时，给k分配了多少钱?
    if x == 0:
        val = 0
        amount = 0
    elif k == 1:
        val = f[1][x]
        amount = x
    else:
        val = -1  # 求最大值

        for xk in range(x + 1):  # 对给定项目k，枚举所有的分配钱数。
            # 投资给fk xk的前，剩下的前交给子问题。
            temp = f[k][xk] + DP_Recur(k - 1, x - xk, mem, solution)
            if temp > val:
                amount = xk
                val = temp
    mem[k, x] = val
    # 给项目k分配了amount，则子问题达到最大值。
    solution[k, x] = amount
    return val


def DP_Iter():
    """
    迭代求解，打表。
    """
    dp = {}
    solution = {}
    # 对边界条件进行初始化（边界条件就是初始条件）
    # 1. x=0，所有子问题的解都是0
    # 2. k=1，只对f1进行投资，子问题的解就等于f1(x)
    for k in range(1, N + 1):
        dp[k, 0] = 0
        solution[k, 0] = 0
    for x in range(0, M + 1):
        dp[1, x] = f[1][x]
        solution[1, x] = x

    # 依次考虑项目k。
    for k in range(2, N + 1):  # k=2,...,n
        # 依次考虑钱数的上限。
        for x in range(1, M + 1):  # x=1,...,m
            # 依次考虑x的各种分配方案。
            max_val = -1
            amount = None
            for xk in range(0, x + 1):
                temp = f[k][xk] + dp[k - 1, x - xk]
                if temp > max_val:
                    max_val = temp
                    amount = xk
            dp[k, x] = max_val
            solution[k, x] = amount
   
    print("dp", dp)
    print("solution", solution)
    return dp[N, M], TrackSolution(solution)


def DP_Recur_Solve():
    solution = {}
    mem={}
    max_payback = DP_Recur(N, M, mem, solution)
    allocation = TrackSolution(solution)
    print("dp", mem)
    print("solution", solution)
    return max_payback, allocation


def TrackSolution(solution):
    "还原解向量"
    ans = []
    money = M  # 从后往前追溯。

    for k in range(N, 0, -1):  # 求出N个分量。
        # 当解决子问题 dp[k][x] 时，分配给项目k多少钱？
        val = solution[k, money]
        ans.append(val)
        money -= val
    ans.reverse()
    return ans


def main():
    max_payback, allocation = DP_Iter()
    print(max_payback)
    print(allocation)


main()
